package leetcode100

// TODO 二分查找 [经典] 【-】 在排序数组中查找元素的第一个和最后一个位置
// TODO https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/by-pandaoknight-51pt/

func searchRange(nums []int, target int) []int {
	n := len(nums)
	res := []int{-1, -1}
	l, r := 0, n-1
	sign := -1

	for l <= r {
		mid := (l + r) / 2
		if nums[mid] == target {
			sign = mid
			break
		} else if nums[mid] > target {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}

	if sign == -1 {
		return res
	}

	for i := sign; i >= 0; i-- {
		if nums[i] == target {
			res[0] = i
		}
	}

	for i := sign; i < n; i++ {
		if nums[i] == target {
			res[1] = i
		}
	}

	return res
}
